Railgun

题意

给定 $n,a,b$，你现在在 $0$ 处跳格子，每次可以向前跳 $a$ 格或者 $b$ 格。

求到达 $n$ 格的方案数，答案对 $10,007$ 取模。$(n,a,b\in[1,10^9])$

CF1305G-Kuroni and Antihype

给定的数据范围是一个弱化版本。

题意

给定 $n$ 个点权 $\{a\}$，并按照规则：对于 $i,j$，如果 $i \& j=0$ 则对 $i,j$ 连边，生成图 $G$。

现在要求 $G$ 中的每个点都要按照如下规则加入集合 $S$：

1. 直接将点 $i$ 加入集合 $S$，贡献为 0；
2. 如果集合中已经存在点 $j$ 且点 $i,j$ 之间存在连边，那么将 $i$ 加入集合 $S$，贡献为 $a_i$。

求最大贡献，$n\leq 2\times10^3,a_i\leq10^9$。

CF1375G-Tree Modification

题意

给定一棵有 $n$ 个结点的树，每次操作选取 3 个点 $i,j,k$ 满足 $i,j$ 存在连边，$j,k$ 存在连边，定义一次操作为：

1. 将 $i$ 的所有出边删除。
2. 将原先除去 $j$ 外与 $i$ 存在连边的点与 $k$ 连边。
3. 连接 $i,k$ 两点。

求最小的操作次数使得树存在度为 $n-1$ 的点。

Teleport

题意

给定一个长度为 $n$ 的序列 $\{a\}$，$q$ 次询问。每次查询区间 $[l,r]$，若能选出 1 个三元组 $(a_i,a_j,a_k)$ 使得能够构成三角形，输出 Triangle，否则输出 Not triangle。注意 $i\ne j,j\ne k$，$n\leq 2\times 10^5,a_i\leq10^9$。

Electro Master

上午唯一写出的题。

题意

给定 $n$ 个矩形，值域范围 $r\times c$，求有被至少 $n-1$ 个矩形覆盖的位置数目。

洛谷-P3198 [HNOI2008]遥远的行星

题意

现在给定一个序列 $\{a\}$，令 $f(i,j)=\frac{a_i \times a_j}{j-i}$。对于每个 $i$，计算出所有满足 $j\leq i \times k$ 的 $f(i,j)$，（其中 $k$ 为一个小于 $0.35$ 的常量），相对误差小于 $5\%$。

ATCoder-[ABC176F] Brave CHAIN

题好我非，交了 14 遍才过，一直 RE，原因是储存修改的数组开小了，然而以为是在调用存值的时候数组越界，从下午调到晚上。

ATCoder-[ABC179F] Simplified Reversi

周末的赛题，然而考场上因为 E 题的一点细节没处理好，只剩下 30 min 来写 F，想到了做法后索性就没写 Code 了。

背包动态规划复习

01背包

考虑到最多只能选取1个，反向枚举顺序满足当前决策不会影响到同一个物品的其他决策。

朴素枚举 $\text{O}(nv)$

for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--){
	dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
}

洛谷-P1048 采药

##P4163 [SCOI2007]排列

本着来写状压的，奈何发现手算一波复杂度后感觉不对。

那么我们考虑搜索（$n\leq10$），暴力搞的话复杂度为 $\text{O}(n!\times T)$，无法通过。

那么我们考虑使用一点点的状压思想和搜索技巧：